This invention relates generally to computer networks and, more particularly, to efficient reassembly of data packets in an intermediate station of a computer network.
A computer network is a geographically distributed collection of interconnected communication media for transporting data between entities. An entity may consist of any device, such as a host or end station, that sources (i.e., transmits) and/or receives network messages over the communication media. Many types of computer networks are available, with the types ranging from local area networks (LANs) to wide area networks (WANs). The end stations, which may include personal computers or workstations, typically communicate by exchanging discrete messages, such as frames or packets, of data according to predefined protocols. In this context, a protocol consists of a set of rules defining how the stations interact with each.
Computer networks may be further interconnected by an intermediate station, such as a switch or router, having a plurality of ports that may be coupled to the networks. For example, a switch may be utilized to provide a xe2x80x9cswitchingxe2x80x9d function for transferring information between a plurality of LANs at high speed. Typically, the switch operates at the data link layer of a communications protocol stack (layer 2) in accordance with the IEEE 802.1D standard to receive a data packet at a source port that originated from a sending entity and forward that packet to at least one destination port for transfer to a receiving entity.
On the other hand, a router may be used to interconnect LANs executing different LAN standards and/or to provide higher level functionality than is typically provided by the switch. Routers typically operate at the network layer (layer 3) of a communications protocol stack, such as the Internet communications architecture protocol stack. The primary network layer protocol of the Internet architecture is the Internet protocol (IP) that provides internetwork routing and that relies on transport protocols for end-to-end reliability. An example of such a transport protocol is the Transmission Control protocol (TCP) contained within a transport layer (layer 4) of the Internet architecture. The term TCP/IP is commonly used to refer to the Internet architecture; the TCP/IP architecture is well known and described in Computer Networks, 3rd Edition,xe2x80x9d by Andrew S. Tanenbaum, published by Prentice-Hall (1996).
It is generally common to configure switches that operate at layer 3 of the communications protocol stack and, in fact, switches may be further configured with the capability to examine information contained within a layer 4 header of a packet. This trend may lead to higher layer (xe2x80x9clayer 4/7xe2x80x9d) switches that are capable of rendering decisions (e.g., forwarding and routing decisions) by analyzing higher layer (e.g., application layer 7) data. In order to perform such higher layer decision operations, the switch must be capable of fragmenting a packet to examine the information contained in its higher layer headers and then reassembling the packet prior to forwarding it to at least one of its destination ports. In the context of a TCP/IP networking environment, the fragmentation and reassembly procedure is well known and described in detail in the Internet Protocol, Request for Comments (RFC) 791, by Information Sciences Institute University of Southern California (1981), which disclosure is hereby incorporated by reference.
Fragmentation of an IP datagram (hereinafter referred to as a packet) is also necessary if the LAN standards associated with the source and destination entities are dissimilar (e.g., Ethernet and Token Ring). In this case, the switch may need to alter the format of the packet so that it may be received by the destination entity. For example, if a packet originates in a network that allows a large packet size and traverses one or more links or local networks that limit the packet to a smaller size, the switch interconnecting the networks must fragment the IP packet. According to RFC 791, IP fragmentation apportions an IP packet into an arbitrary number of fragments that can be later reassembled.
FIG. 1 is a schematic block diagram of an IP packet 100 comprising an IP header portion 110 and a payload/data portion 150. The IP header 110 comprises a version field 102 that indicates the format of the IP header, an Internet header length (IHL) field 104 that indicates the length of the Internet header and a type of service (TOS) field 106 that provides an indication of parameters of a desired quality of service. An IP total length field 108 specifies the length of the IP packet including the IP header and payload/data, while an IP identification field 110 specifies an identifying value assigned by the sending entity to aid in assembling the fragments of the packet.
The IP header further includes a more fragment (MF) flag 112, an IP fragment offset field 114 that specifies the placement of the fragment within the IP packet and a time to live (TTL) field 116 that indicates a maximum time the packet is allowed to remain in the network. A protocol field 118 indicates the next level protocol used in the payload/data portion 150 of the packet, while a header checksum field 120 provides a checksum on only the IP header. The IP header further includes a source address field 122 containing the IP source address of the sending entity and a destination address field 124 containing the IP destination address of the receiving entity, along with an options field 126 and a padding field 128.
To fragment an IP packet, an intermediate system (e.g., a switch) creates two or more new IP fragments and copies the contents of a portion of the IP header fields from the original packet into each of the IP headers of the fragments. The receiving entity of the fragments uses the contents of the IP identification field 110 to ensure that fragments of different packets are not mixed. That is, the identification field 110 is used to distinguish the fragments of one packet from those of another. The IP fragment offset field 114 informs the receiving entity about the position of a fragment in the original packet. The contents of the fragment offset field and the IP total length field 108 of each fragment determine the portion of the original packet covered by the fragment. The MF flag 112 indicates (e.g., when reset) the last fragment. The originating host of a complete IP packet sets the IP identification field 110 to a value that is unique for the source/destination address pair and protocol (e.g., TCP, UDP) for the time the packet will be active in the network. The originating host of the complete packet also sets the MF flag 112 to, e.g., zero and the IP fragment offset field 114 to zero.
The IP fragmentation and reassembly procedure is typically not performed by intermediate stations, but rather by host end stations in a network. For those intermediate stations (switches) that implement the procedure, the functions are typically performed in software using general-purpose processors. The amount of processing required to identify information inside an IP packet is substantial and a general-purpose processor may not have an architecture that is optimized to efficiently perform such processing. Moreover software implementation of IP packet reassembly introduces a critical bottleneck in packet processing operations at the switch.
In an IP network environment, higher layer (e.g., layer 4/7) switches must reassemble fragments traversing the network into the original packet before processing the packet. To reassemble the fragments of an IP packet, the switch or host end station typically pre-allocates a buffer and then combines fragments having a similar 4-tuple arrangement comprising {IP identification, IP source, IP destination and IP protocol} values. Reassembly of the fragments is performed by placing the data portion of each fragment in a relative position indicated by the IP fragment offset of that fragment""s IP header. However, pre-allocation of a buffer is undesirable in an intermediate station because it results in inefficient use of memory due to the varying number of fragments/fragmented packets received at the switch and facilitates attacks by intruders (xe2x80x9chackersxe2x80x9d) that employ fragmentation to saturate resources (such as memory) of the switch.
The invention relates to an IP packet reassembly engine that provides high-speed and efficient reassembly of IP fragments received at an intermediate station in a computer network. The IP packet reassembly engine preferably comprises a main controller logic circuit configured to xe2x80x9cspeed-upxe2x80x9d reassembly of original packets from IP fragments stored in a frame buffer at multi-gigabit per second rates. To that end, the reassembly engine further includes a content addressable memory (CAM) having a plurality of entries for maintaining status information for each received fragment and for each original packet being reassembled from the fragments.
In the illustrative embodiment, the main controller of the IP reassembly engine comprises, inter alia, a frame buffer controller that cooperates with queuing and dequeuing logic to store and retrieve fragments to/from queues of the frame buffer. An input queue data structure is provided within the main controller for managing the queues of the frame buffer. The main controller is responsible for deciding whether a packet received by the IP reassembly engine is complete by checking status information maintained by the CAM subsystem. The main controller also manages the CAM by deleting packet entries and all related fragment entries that have expired. This latter task is performed in accordance with a timer handling process that periodically compares a current time with an expiration time stored in an expiration time field of each CAM entry.
Specifically, the CAM subsystem stores information about the length of each packet currently being reassembled. That is, the CAM maintains information about the IP total length of each packet and the accumulated (i.e., current) length of all received fragments belonging to that packet. The information relating to these two length parameters indicate whether all fragments belonging to a particular packet have been received. The IP total length of the reassembled packet is derived from the last fragment of the packet by adding its IP fragment offset and its IP total length. Note that the last fragment may comprise the last received fragment or the fragment having a reset MF flag. When the current length equals the total length for a given packet, the reassembly process starts and the packet is assembled starting with its first fragment whose pointer to the frame buffer is stored in the CAM.
Operationally, a first lookup operation is performed in the CAM to find a first xe2x80x9coffset zeroxe2x80x9d fragment of a packet using, for example, a class of service (COS) field and an input index (IDX) field as the lookup key. Once found, the contents of a pointer (PTR) field and a total length (TLEN) field are retrieved, along with information (i.e., IP destination, IP source, IP protocol and IP identification) stored in a 4-tuple field of the CAM. The pointer is used to retrieve the fragment from a queue in the frame buffer. All subsequent fragments of the packet are retrieved from the frame buffer based on a 4-tuple search of the CAM to obtain pointers to the respective queues in the buffer.
The fragments are reassembled into proper order within a packet by placing the data portion of each fragment in a relative position indicated by the IP fragment offset of each fragment. During reassembly of the packet, each lookup operation varies from the previous one by the fragment offset value, which is calculated as:
xe2x80x83FragmentOffsetn+1=FragmentOffsetn+IPTotalLengthn
The reassembly process completes when the last fragment (i.e., the fragment having MF flag=0) has been added to the reassembled original packet. The time needed to reassemble a packet increases linearly with the number of fragments.
In summary, the IP reassembly logic engine is an efficient logic circuit, based on the use of a CAM, for implementing packet reassembly in an intermediate station, such as a layer 4/7 switch. Advantages of reassembling original packets at an intermediate station include (i) off-loading of the reassembly process from host end stations, (ii) the ability to defend a private LAN network from intruders/hackers, and (iii) the ability to perform higher layer (layer 4-7) operations. These latter operations include load balancing, web cache redirection and uniform resource locator (URL) inspection, along with filtering (access list) based on layer 4 (TCP) ports.